"""

Computational Economics
2.4: Application: Shortest Paths and Dynamic Programming
http://johnstachurski.net/lectures/short_path.html


    Use this algorithm:

    ----------
    ALGORITHM:

        The standard algorithm for finding J is to start with

            J0(v) = M if v != destination, else J0(v) = 0

        where M is a big number

        Now we use the following algorithm

            1. Set n = 0
            2. Set

                Jn+1(v) = min{c(v,w) + Jn(w)} for all v

            3. If Jn+1 and Jn are not equal then increment n, go to 2

        In general, this sequence converges to J---the proof is omitted
    ---------

    ...to find the optimal path (and its cost) for this graph: graph.txt.

    Here the line

    node0, node1 0.04, node8 11.11, node14 72.21

    means that from node0 we can go to

        * node1 at cost 0.04
        * node8 at cost 11.11
        * node14 at cost 72.21

    And so on, and so on

"""

from os.path import (dirname, join)
import random
from datetime import date

THIS_DIR    = dirname(__file__)
FNAME       = 'graph.txt'
DATA_FILE   = join(THIS_DIR, FNAME)

def read_graph_file(path):
    """
    Read graph file into a list of dicts:
        [ {'node1': 1.0, 'node2': 2.0}, {'node2': 1.0, 'node3': 2.0}, ... ]
    """
    graph_list = []
    f = open(path)
    lines = f.readlines()
    f.close()

    graph_dict = {}
    for line in lines:
        node_dict = {}
        line_items = [item.strip() for item in line.split(',')]
        key = line_items[0]

        if key == 'node99':
            graph_dict['node99'] = None
            break

        for item in line_items[1:]:
            #print item
            node, cost = item.split(" ")
            node_dict[node] = float(cost)
        graph_dict[key] = node_dict

    #print random.sample(graph_dict, 3)
    assert graph_dict['node86'] == { 'node97': 85.09 }
    return graph_dict

def bellmans_equation(node_chain, total_cost, graph):
    """Let J(v) denote the minimum cost-to-go from node v

    Jn+1(v) = min{c(v,w) + Jn(w)} for all v

    * Fv is the set of nodes which can be reached from v in one step
    * c(v, w) is the cost of traveling from v to w

    Return tuple(list of nodes, cost)

    INPUTS
    node_chain: list of nodes traversed thus far
    chain_cost: total cost of chain thus far
    last node: last nodes name
    graph: the whole graph (a dict of dicts)

    RETURN
    the lowest cost of next step among alternative in form of tuple containing:
    (list of nodes in order, total cost)
    """
    current_node = node_chain[-1]
    neighbor_nodes = graph[current_node]
    #print 'START', node_chain, total_cost, neighbor_nodes

    if not neighbor_nodes:
        #print 'END %s -> %s: %s' % (node_chain[0], current_node, total_cost)
        return node_chain, total_cost

    neighbor_costs = []
    for node in neighbor_nodes:
        costv = neighbor_nodes[node]
        next_node, costw = bellmans_equation([node], total_cost+costv, graph)
        neighbor_costs.append((node_chain + next_node, costw))

    sorted_costs = sorted(neighbor_costs, key=lambda tup: tup[1], reverse=False)
    #print 'SORT', sorted_costs
    return sorted_costs[0]


def simpler_test():
    graph = {
        'node0' : {'node1': 1, 'node2': 1},
        'node1' : {'node3': 1},
        'node2' : {'node3': 2},
        'node3' : None,
    }
    min_route, cost = bellmans_equation(['node0'], 0, graph)
    print 'SOLVED:', min_route, cost
    assert cost == 2


def simple_test():
    graph = {
        'nodeA' : {'nodeC': 5, 'nodeD': 3, 'nodeB': 1},
        'nodeB' : {'nodeD': 9, 'nodeE': 4},
        'nodeC' : {'nodeF': 2},
        'nodeD' : {'nodeF': 4, 'nodeG': 8},
        'nodeE' : {'nodeG': 4},
        'nodeF' : {'nodeG': 1},
        'nodeG' : None,
    }

    min_route, cost = bellmans_equation(['nodeA'], 0, graph)
    print 'SOLVED:', min_route, cost
    assert cost == 8


def solve_graph():
    graph = read_graph_file(DATA_FILE)
    min_route, cost = bellmans_equation(['node0'], 0, graph)
    print 'SOLVED:', min_route, cost

    # verify (from )
    chain = """
node0
node8
node11
node18
node23
node33
node41
node53
node56
node57
node60
node67
node70
node73
node76
node85
node87
node88
node93
node94
node96
node97
node98
node99
"""
    expected_route = [n.strip() for n in chain.split("\n") if n.strip() != ""]
    expected_cost = 160.55
    assert int(cost * 100) == int(expected_cost * 100)
    assert min_route == expected_route


#
# Stachurski Solution
#
def read_graph():
    """ Read in the graph from the data file.  The graph is stored
    as a dictionary, where the keys are the nodes, and the values
    are a list of pairs (d, c), where d is a node and c is a number.
    If (d, c) is in the list for node n, then d can be reached from
    n at cost c.
    """
    graph = {}
    infile = open(DATA_FILE)
    for line in infile:
        elements = line.split(',')
        node = elements.pop(0).strip()
        graph[node] = []
        if node != 'node99':
            for element in elements:
                destination, cost = element.split()
                graph[node].append((destination.strip(), float(cost)))
    infile.close()
    return graph

def print_best_path(J, graph):
    """ Given a cost-to-go function, computes the best path.  At each node n,
    the function prints the current location, looks at all nodes that can be
    reached from n, and moves to the node m which minimizes c + J[m], where c
    is the cost of moving to m.
    """
    sum_costs = 0
    current_location = 'node0'
    best_path = []

    while current_location != 'node99':
        best_path.append(current_location)
        running_min = 1e100  # Any big number
        for destination, cost in graph[current_location]:
            cost_of_path = cost + J[destination]
            if cost_of_path < running_min:
                running_min = cost_of_path
                minimizer_cost = cost
                minimizer_dest = destination
        current_location = minimizer_dest
        sum_costs += minimizer_cost

    return best_path, sum_costs


def update_J(J, graph):
    "The Bellman operator."
    next_J = {}

    for node in graph:
        if node == 'node99':
            next_J[node] = 0
        else:
            next_J[node] = min(cost + J[dest] for dest, cost in graph[node])

    # update status
    status_update = []
    status_nodes = [0, 20, 40, 60, 80, 98]
    for n in status_nodes:
        node = 'node%s' % (n)
        status_update.append((node, '%.1f' % (next_J[node])))
    print 'bellman:', status_update

    return next_J


def stachurski_solution():
    graph = read_graph()
    M = 10000
    J = {}
    for node in graph:
        J[node] = M
    J['node99'] = 0

    while 1:
        next_J = update_J(J, graph)
        if next_J == J:
            break
        else:
            J = next_J
    best_path, cost = print_best_path(J, graph)
    print [(node, '%.2f' % (J[node])) for node in best_path]
    print cost






def main():
    stachurski_solution()




#
# MAIN
#
main()
print '%s: ok' % (__file__)

